package org.basis.algorithm.sort;

import org.basis.algorithm.sort.common.SortUtil;

import java.util.Arrays;

/**
 * 插入排序: 类似于玩扑克牌，从0位置开始依次往后，对于每一张牌向前找到他合适的位置
 *
 * @author Mr_wenpan@163.com 2022/01/26 15:55
 */
public class InsertionSort {

    public static void main(String[] args) {
        final int num = 10000;
        for (int i = 0; i < num; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            sort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("fuck!");
            }
        }
    }

    /**
     * 插入排序: 类似于玩扑克牌，从0位置开始依次往后，对于每一张牌向前找到他合适的位置
     */
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            // 每一轮从剩下的牌中选择一张最小的插入到 i 位置
            for (int j = i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    SortUtil.swap(i, j, arr);
                }
            }
        }
    }

}
